package Greedy.leetcode;

import java.util.Arrays;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class K次取反后最大化的数组和 {
    public static void main(String[] args) {

    }

    /**
     * 代码逻辑：
     *      1. 对A排序
     *      2. 统计A中负数的个数count
     *      3. 将count和取反次数进行比较
     *          1. count > k 直接求和 负数进行取反求和(前k个取反求和)
     *          2. count = k 直接求和 负数取反(所有负数)
     *          3. count < k
     *              此时的取法次数多余负数的个数，我们对k进行预处理
     *              k -= count // 将所有负数取反，此处用取法次数减去count代替取法操作
     *              k %= 2 // 最终需要取反的次数 注意：对于正数而言偶数周期的取反还是本身
     *              分类：
     *                  1. count = 0  k = 0
     *                  2. count = 0  k = 1
     *                  3. count != 0 k = 0
     *                  4. count != 0 k = 1
     *       下面的代码总体时间复杂度由排序决定的，代码比较冗余，分类的情况太多了，可以优化的点有很多
     * @param A
     * @param K
     * @return
     */
    public int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A); // 将数组中的元素按照升序排列
        int ans = 0; // 记录结果
        int count = 0; // 记录数组中负数的个数
        for(int num : A) {
            count = (num < 0) ? count+1 : count;
        }
        // 考虑负数元素的个数和k之间的关系
        if(count == K) {
            // 恰好等于，直接将负数取反求和即可
            for(int num : A) {
                ans += (num >= 0) ? num : -num;
            }
            return ans;
        }
        if(count > K) {
            // 负数个数多余取反的此时，将前k个最小的负数取法求和
            for(int i = 0; i < A.length; i++) {
                ans += (i < K) ? -A[i] : A[i];
            }
            return ans;
        }
        if(count < K) {
            K -= count;
            K %= 2; // 最终取法的此时为0或者1
            if(count == 0) {
                // 如果没有负数
                if(K == 0) {
                    for(int num:A) {ans+=num;}
                    return ans;
                }
                if(K == 1) {
                    for(int i = 0; i < A.length; i++) {
                        ans += (i == 0) ? -A[i] : A[i];
                    }
                    return ans;
                }
            }
            if(K == 0) {
                for(int num:A) {
                    ans += (num < 0) ? -num : num;
                }
                return ans;
            } else {
                // k = 1, count != 0
                for(int i = 0; i < A.length; i++) {
                    A[i] = (i < count) ? -A[i] : A[i];
                }
                Arrays.sort(A);
                for(int i = 0; i < A.length; i++) {
                    ans += (i == 0) ? -A[i] : A[i];
                }
                return ans;
            }
        }
        return -1;
    }
}
